package com.test.daily.leetcode.y2022.m07.day0716.v03;

import java.util.HashMap;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/7/16 下午 01:56
 * @version: 1.0
 */
public class Solution {
    public static class Node{
        int value;
        Node next;
        Node random;
        public Node(int value){
            this.value = value;
        }
    }
    public static Node copyWithRandomNode(Node root){
        Node cur = root;
        HashMap<Node, Node> map = new HashMap<>();
        while(cur != null){
            map.put(cur, new Node(cur.value));
            cur = cur.next;
        }
        cur = root;
        while(cur != null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
        }
        return map.get(root);
    }
    public static Node copyWithRandom2(Node root){
        Node cur = root;
        while(cur != null){
            Node next = cur.next;
            cur.next = new Node(cur.value);
            cur.next.next = next;
            cur = next;
        }
        cur = root;
        while(cur != null){
            Node next = cur.next.next;
            Node curCopy = cur.next;
            curCopy.random = cur.random == null ? cur.random.next:null;
            cur = next;
        }
        cur = root;
        Node copy = root.next;
        while(cur != null){
            Node next = cur.next.next;
            Node curCopy = cur.next;
            cur.next = next;
            curCopy.next = next != null ? next.next: null;
            cur = next;
        }
        return copy;
    }
}
